\chapter{Teknik Greedy}


\ifthenelse{\boolean{adaTIU}}{
	\begin{footnotesize}
	  \begin{description}
	  \item[Tujuan Pembelajaran]:
	  \begin{itemize}
			\item Memberikan penjelasan mengenai algoritma yang menggunakan teknik Greedy dan masalah yang dapat diselesaikan dengan teknik tersebut
			\item Memberikan penjelasan mengenai algoritma Minimum Spanning Tree
			\item Memberikan penjelasan mengenai algoritma shortest path Dijkstra
			\item Memberikan penjelasan mengenai Pengkodean Huffman
		\end{itemize}
		\item[Setelah menyelesaikan modul ini mahasiswa diharapkan dapat]:
		\begin{itemize}
			\item Menjelaskan masalah Minimum Spanning Tree
			\item Menuliskan algoritma, membuat program dan menurunkan kompleksitas MST Prim
			\item Menuliskan algoritma, membuat program dan menurunkan kompleksitas MST Kruskal
			\item Menuliskan algoritma, membuat program dan menurunkan kompleksitas Shortest Path Dijkstra
			\item Menjelaskan masalah Pengkodean Huffman
			\item Menuliskan algoritma, membuat program dan menurunkan kompleksitas Pengkodean Huffman
		\end{itemize}
		\item[Kata kunci]:
		\begin{itemize}
		  \item Minimum Spanning Tree, MST Prim, MST Kruskal, Shortest path Dijkstra, Pengkodean Huffman
		\end{itemize}
		\end{description}
	\end{footnotesize}
}


\section{Pendahuluan}

Bab ini membahas kelompok masalah yang dipecahkan dengan menggunakan \index{greedy technique@\emph{greedy technique}} teknik \emph{greedy}. Masalah-masalah yang termasuk ke dalam kelompok ini biasanya adalah masalah-masalah \index{optimal problem@\emph{optimal problem}} pencarian solusi optimal. Sesuai dengan namanya, \emph{greedy} dapat kita terjemahkan secara harfiah sebagai "serakah" atau "rakus". Teknik ini secara bertahap mencari solusi akhir melalui serangkaian pencarian sub-solusi. Dalam hal ini teknik \emph{greedy} memiliki kemiripan dengan teknik \emph{decrease and conquer} pada Bab~\ref{ch:decrease-and-conquer}. Perbedaannya terletak pada pilihan sub-solusi yang diambil. Pada teknik \emph{greedy}, secara 'serakah' teknik ini mengambil sub-solusi yang 'terbaik'.

Perlu diperhatikan bahwa pencarian sub-solusi 'terbaik' tergantung dari sifat masalah yang sedang dihadapi. Ada kalanya sub-solusi 'terbaik' kita ambil berdasarkan nilai minimum, dalam kasus yang lain kita dapat mengambil sub-solusi berdasarkan nilai maksimum. Perlu diperhatikan pula bahwa kadang-kadang solusi akhir yang dihasilkan dari pemilihan dengan teknik \emph{greedy} bukan merupakan solusi yang paling optimal. Hal ini disebabkan karena algoritma greedy akan langsung menganggap pilihan terbaik dalam tahap pencarian sub-solusi sebagai bagian dari solusi permasalahan akhir tanpa mengecek keberadaan kemungkinan-kemungkinan lain yang mungkin saja lebih tepat menjadi solusi akhir yang paling optimal. Namun demikian dalam banyak permasalahan, teknik \emph{greedy} dapat memberikan solusi akhir terbaik. Salah satu hal yang merupakan kelebihan dari teknik ini adalah singkatnya waktu yang diperlukan dalam menyelesaikan masalah.

Bab ini mengemukakan beberapa contoh permasalahan yang dapat diselesaikan dengan algoritme yang menggunakan teknik \emph{greedy}, yaitu pencarian \emph{minimum spanning tree} (MST), baik dengan metoda Kruskal maupun Prim, pencarian jarak terpendek dari satu verteks ke verteks lainnya yang ada dalam sebuah graf (\emph{shortest path}) serta pengkodean Huffman.


\section{Minimum Spanning Tree}

\index{minimum spanning tree@\emph{Minimum Spanning Tree}} \index{mst@MST} \emph{Minimum Spanning Tree} (MST) merupakan salah satu persoalan optimasi yang sering ditemui dalam kehidupan sehari-hari. Sebagai contoh, perancangan jalur transmisi listrik yang dapat menghubungkan beberapa kota dengan biaya minimal dapat menggunakan metode pencarian MST. Tujuan dari perancangan tersebut adalah bagaimana meminimalkan panjang kabel yang menghubungkan setiap kota dengan kota lain. Semakin pendek panjang kabel yang terentang, maka akan semakin murah biaya yang diperlukan untuk menghubungkan kota-kota tersebut dalam sebuah jaringan transmisi listrik.

Contoh permasalahan di atas dapat dimodelkan dalam bentuk \index{graf!berbobot} \index{graph@\emph{graph}!weighted@\emph{weighted}} graf berbobot (\emph{weighted graph}), di mana setiap kota merupakan verteks dan jalur transmisi yang menghubungkan antar kota adalah edge. Setiap edge memiliki bobot atau \emph{weight} yang menyatakan biaya yang diperlukan untuk merentangkan kabel listrik dari satu kota ke kota yang lain. Perhatikan bahwa dalam masalah ini kita tidak memperdulikan jalur yang dipilih untuk menghubungkan seluruh kota, yang menjadi inti masalahnya adalah bagaimana mencari panjang kabel terpendek. Bila seluruh kemungkinan jalur transmisi dan biaya pembangunan setiap jalur tersebut  diketahui, maka jalur transmisi yang dapat menghubungkan seluruh kota dengan biaya minimal tidak lain adalah \emph{minimum spanning tree} dari model graf tersebut.

MST suatu graf dapat dipandang sebagai himpunan edge, yang menghubungkan semua verteks pada graf dengan bentuk \emph{tree} di mana jumlah total \emph{weight} dari seluruh edge yang membentuk \emph{tree} bernilai minimum. Dengan pengertian tersebut suatu MST dapat dibangun mulai dari suatu himpunan kosong. Selanjutnya pada himpunan tersebut ditambahkan anggota baru di antara edge yang memenuhi syarat \index{safe edge@\emph{safe edge}} (\emph{safe edge}), yaitu yang mempunyai \emph{weight} terkecil.
Karena MST merupakan suatu \emph{tree}, yaitu \emph{connected graph} yang tidak mempunyai \emph{cycle}, maka \emph{safe edge} adalah edge yang tidak menyebabkan munculnya \emph{cycle}.

Algoritma dasar tersebut dapat dituliskan seperti diperlihatkan pada Algoritme~\ref{alg:generic-mst}.

\begin{algorithm}
\begin{algorithmic}[1]
	\STATE \textsc{Generik MST} $(G)$
	\COMMENT Inisialisasi $F$ sebagai himpunan kosong dari edge
	\STATE $F \leftarrow \emptyset$
	\WHILE{$F$ belum membentuk MST}
		\STATE Cari edge $(u,v)$ yang memenuhi syarat untuk digabung dengan $F$
		\STATE $F \leftarrow F \cup (u,v)$
	\ENDWHILE
	\STATE return $F$
\end{algorithmic}
\caption{Algoritme MST generik.} \label{alg:generic-mst}
\end{algorithm}

\subsection{Algoritma Kruskal}

Dengan menggunakan prinsip dari Algoritme~\ref{alg:generic-mst} \index{kruskal@Kruskal} Kruskal membangun MST dengan cara memilih di antara edge yang ada mulai dari yang terkecil. Perhatikan Algoritme~\ref{alg:kruskal}. Langkah pertama yang dilakukan adalah mengurutkan semua edge di dalam graf secara terurut berdasarkan bobotnya, mulai dari bobot terkecil. Secara bertahap algoritme Kruskal mengambil satu per satu edge dari daftar yang sudah terurut tadi dan dimasukkan ke dalam bagian dari MST. Setiap kali sebuah edge diambil, perlu diperiksa terlebih dahulu apakah jika edge tersebut diambil akan membentuk \emph{cycle}. Jika tidak membentuk \emph{cycle}, maka edge tersebut diambil sebagai bagian dari MST. Proses ini dilakukan terus hingga semua edge dalam daftar terurut habis diperiksa apakah memang merupakan bagian dari MST atau bukan.

Pengecekan adanya \emph{cycle} yang terjadi dapat dilakukan dengan memeriksa verteks yang \emph{incident} dengan edge yang sedang diperiksa. Setiap edge pasti ber-\emph{incident} dengan dua buah verteks. Ketika sebuah edge diperiksa apakah dia merupakan bagian dari MST atau bukan, kita perlu memeriksa apakah edge tersebut akan membentuk \emph{cycle}. \emph{Cycle} akan terbentuk apabila kedua verteks yang ber-\emph{incident} dengan edge tersebut sudah merupakan bagian dari MST yang sudah terbentuk. Jika salah satu verteks bukan merupakan bagian dari MST yang sudah terbentuk, maka edge tersebut pasti merupakan bagian dari MST berikutnya.

\begin{algorithm}
\begin{algorithmic}[1]
	\STATE \textsc{MSTKruskal} $(G)$
	\COMMENT $G$ adalah graf yang akan dicari MST-nya.
	\STATE $L \leftarrow e \in G$ terurut secara ascending berdasarkan bobot.
	\STATE $A \leftarrow \emptyset$
	\STATE $B \leftarrow \emptyset$
  \STATE $f \leftarrow$ remove-first-element$(L)$
  \STATE $A \leftarrow A \cup f$
  \STATE $u,v \leftarrow $ verteks yang \emph{incident} dengan $f$
  \STATE $B \leftarrow B \cup u \cup v$
	\WHILE{$L \neq \emptyset$}
	  \STATE $f \leftarrow$ remove-first-element$(L)$
	  \STATE $u,v \leftarrow $ verteks yang \emph{incident} dengan $f$
	  \IF{$u \notin B$ OR $v \notin B$}
	    \STATE $A \leftarrow A \cup f$
	    \STATE $B \leftarrow B \cup u \cup v$
	  \ENDIF
	\ENDWHILE
\end{algorithmic}
\caption{Algoritme Kruskal.} \label{alg:kruskal}
\end{algorithm}

\subsection{Algoritma Prim}

\index{prim@Prim} Algoritme Prim memulai pembuatan MST dari satu verteks yang ditentukan, disebut sebagai \emph{source vertex}. Pemilihan \emph{source vertex} dapat dilakukan secara bebas, tanpa ada batasan verteks yang mana yang harus dijadikan sebagai titik awal. \emph{Source vertex} ini digunakan sebagai informasi untuk membentuk sebuah konfigurasi yang disebut \index{graf!cut@\emph{cut}} \emph{cut}.

\emph{Cut} dari sebuah graf adalah konfigurasi di mana himpunan verteks dari graf tersebut dipisahkan ke dalam dua himpunan terpisah. Jika sebuah graf memiliki himpunan verteks $V = \{v_1, v_2, \ldots, v_n \}$, maka \emph{cut} dapat dibentuk dengan membuat dua sub-himpunan $A \subseteq V$ dan $B \subseteq V$ di mana $A \cup B = V$ dan $A \cap B = \emptyset$. Perlu diperhatikan bahwa pemilihan anggota himpunan $A$ dan $B$ dapat dilakukan secara bebas, yang penting irisan kedua himpunan tersebut haruslah himpunan kosong, dan gabungan kedua himpunan itu haruslah membentuk himpunan verteks $V$.

Dari sebuah konfigurasi \emph{cut}, kita dapat membentuk himpunan \index{crossing edge@\emph{crossing edge}} \emph{crossing edge} $CE$. Himpunan ini didefinisikan sebagai edge-edge yang menghubungkan verteks-verteks di $A$ dengan verteks-verteks di $B$. Edge-edge yang menghubungkan verteks-verteks di dalam himpunan $A$ bukan dikatakan sebagai \emph{crossing edge}, demikian pula semua edge yang menghubungkan verteks-verteks anggota himpunan $B$. Anggota himpunan \emph{crossing edge} yang memiliki bobot terkecil disebut sebagai \emph{light edge}.

Algoritme Prim membangun MST berawal dari \emph{source vertex} $v_s$ dengan membentuk sebuah \emph{cut}:
% MathType!Translator!2!1!LaTeX.tdl!TeX -- LaTeX 2.09 and later!
% MathType!MTEF!2!1!+-
% feqaeaartrvr0aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn
% hiov2DGi1BTfMBaeXatLxBI9gBaebbnrfifHhDYfgasaacH8srps0l
% bbf9q8WrFfeuY-Hhbbf9v8qqaqFr0xc9pk0xbba9q8WqFfea0-yr0R
% Yxir-Jbba9q8aq0-yq-He9q8qqQ8frFve9Fve9Ff0dmeaabaqaciGa
% caGaaeqabaaaamaaaOqaauaabaqacmaaaeaacaWGbbaabaGaeyypa0
% dabaGaamODamaaBaaaleaacaWGZbaabeaaaOqaaiaadkeaaeaacqGH
% 9aqpaeaacaWGwbGaeyOeI0Iaamyqaaaaaaa!3A06!
\[
\begin{array}{*{20}c}
   A \hfill &  =  \hfill & { \{ v_s \} } \hfill  \\
   B \hfill &  =  \hfill & {V - A} \hfill  \\
\end{array}
\]
% MathType!End!2!1!
Berdasarkan konfigurasi \emph{cut} ini, kita cari \emph{light edge} yang menghubungkan $v_s$ dengan sebuah verteks di himpunan $B$, $v_{\mathrm{next}}$. \emph{Light edge} ini pasti merupakan bagian dari MST yang kita cari, sehingga edge tersebut kita masukkan ke dalam himpunan edge yang membentuk MST. Karena edge ini menghubungkan $v_s$ dengan sebuah verteks di $B$, maka kemudian kita membentuk sebuah konfigurasi \emph{cut} yang baru, di mana:
% MathType!Translator!2!1!LaTeX.tdl!TeX -- LaTeX 2.09 and later!
% MathType!MTEF!2!1!+-
% feqaeaartrvr0aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn
% hiov2DGi1BTfMBaeXatLxBI9gBaebbnrfifHhDYfgasaacH8srps0l
% bbf9q8WrFfeuY-Hhbbf9v8qqaqFr0xc9pk0xbba9q8WqFfea0-yr0R
% Yxir-Jbba9q8aq0-yq-He9q8qqQ8frFve9Fve9Ff0dmeaabaqaciGa
% caGaaeqabaaaamaaaOqaauaabaqacmaaaeaacaWGbbaabaGaeyypa0
% dabaGaamODamaaBaaaleaacaWGZbaabeaaaOqaaiaadkeaaeaacqGH
% 9aqpaeaacaWGwbGaeyOeI0Iaamyqaaaaaaa!3A06!
\[
\begin{array}{*{20}c}
   A \hfill &  =  \hfill & { \{ v_s \} } \cup \{ v_{\mathrm{next}} \} \hfill  \\
   B \hfill &  =  \hfill & {V - A} \hfill  \\
\end{array}
\]
% MathType!End!2!1!

Iterasi ini kita lakukan secara berulang hingga pada akhirnya kita dapatkan sebuah konfigurasi \emph{cut}:
% MathType!Translator!2!1!LaTeX.tdl!TeX -- LaTeX 2.09 and later!
% MathType!MTEF!2!1!+-
% feqaeaartrvr0aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn
% hiov2DGi1BTfMBaeXatLxBI9gBaebbnrfifHhDYfgasaacH8srps0l
% bbf9q8WrFfeuY-Hhbbf9v8qqaqFr0xc9pk0xbba9q8WqFfea0-yr0R
% Yxir-Jbba9q8aq0-yq-He9q8qqQ8frFve9Fve9Ff0dmeaabaqaciGa
% caGaaeqabaaaamaaaOqaauaabaqacmaaaeaacaWGbbaabaGaeyypa0
% dabaGaamODamaaBaaaleaacaWGZbaabeaaaOqaaiaadkeaaeaacqGH
% 9aqpaeaacaWGwbGaeyOeI0Iaamyqaaaaaaa!3A06!
\[
\begin{array}{*{20}c}
   A \hfill &  =  \hfill & {V} \hfill  \\
   B \hfill &  =  \hfill & \emptyset \hfill  \\
\end{array}
\]
% MathType!End!2!1!

Algoritme~\ref{alg:prim} memberikan langkah-langkah untuk membuat MST dengan cara Prim.

\begin{algorithm}
\begin{algorithmic}[1]
	\STATE \textsc{MSTPrim} $(G)$
	\STATE Pilih $v_s \in V(G)$ secara acak sebagai \emph{source vertex}
	\STATE $mst \leftarrow \emptyset$
	\STATE $A \leftarrow \{ v_s \}$
	\STATE $B \leftarrow V - A$
	\WHILE{$A \neq V$}
	  \STATE Pilih \emph{light edge} $e$ yang menghubungkan $v_{a} \in A$ dengan $v_{\mathrm{next}} \in B$
	  \STATE $mst \leftarrow mst \cup \{ e \}$
	  \STATE $A \leftarrow A \cup \{ v_{\mathrm{next}} \}$
	  \STATE $B \leftarrow V - A$
	\ENDWHILE
	\STATE return $mst$
\end{algorithmic}
\caption{Algoritme Prim.} \label{alg:prim}
\end{algorithm}


\section{Algoritme Dijkstra} \label{algoritme-dijkstra} \label{sect:algoritme-dijkstra}

Dalam suatu graf berbobot, seringkali suatu verteks dapat dicapai dari verteks lain melalui lebih dari satu cara. Dalam hal tersebut seringkali harus dicari lintasan mana yang memiliki bobot terkecil di antara banyak pilihan lintasan. Permasalahan seperti ini dikenal sebagai permasalahan untuk mencari jarak \index{lintasan terpendek} lintasan terpendek atau \index{shortest path@\emph{shortest path}} \emph{shortest path}.

Ada beberapa algoritme yang menjawab masalah lintasan terpendek ini. Salah satunya adalah \index{algoritme!dijkstra@Dijkstra} algoritme Dijkstra. Algoritme ini tergolong ke dalam kelompok algoritme yang memecahkan masalah \index{shortest path@\emph{shortest path}!single source@\emph{single source}} \emph{single source shortest path}. Kelompok masalah ini mencari lintasan terpendek dari \textbf{satu} verteks ke verteks-verteks yang lain di dalam sebuah graf.

Algoritme Dijkstra mencari lintasan terpendek antara dua buah verteks dengan menggunakan \index{prinsip relaksasi} prinsip relaksasi. Misalkan diketahui verteks $u$ dapat dicapai dari verteks $s$ dengan bobot $d_u$. Lintasan dari verteks $s$ ke $u$ tidaklah unik, bisa jadi terdapat kemungkinan lintasan lain yang ditempuh untuk mencapai verteks $u$ dari $s$, katakanlah melalui verteks $v$. Bobot yang diperlukan untuk mencapai verteks $u$ adalah $d_v + d(v,u)$ di mana $d(v,u)$ adalah bobot yang diperlukan untuk mencapai verteks $u$ dari $v$. Jika ternyata nilai $d_u < d_v + d(v,u)$, maka pada saat itu kita tahu bahwa jarak terpendek untuk mencapai $u$ dari $s$ adalah melalui verteks $v$.

Secara algoritmis, prinsip relaksasi ini ditunjukkan dalam Algoritme~\ref{alg:relax}.

\begin{algorithm}
\begin{algorithmic}[1]
	\STATE Relax (u, v, w)
	\IF{Jika d[v] > d[v] + weight(u,v)}
		\STATE d[v] = d[v] + weight(u,v)
		\STATE pred[v] = u
	\ENDIF
\end{algorithmic}
\caption{Algoritme relaksasi.} \label{alg:relax}
\end{algorithm}

Algoritme Dijkstra dimulai dengan mengasumsikan bahwa verteks-verteks selain verteks awal (\emph{source vertex}) tidak dapat dicapai dari verteks awal. Asumsi ini dinyatakan dengan memberi nilai jarak pada verteks-verteks tersebut dengan sebuah nilai $\infty$. Untuk mengetahui lintasan mana yang menghasilkan jarak paling pendek, algoritme Dijkstra juga mencatat \emph{parent} dari sebuah verteks. \emph{Parent} $\pi(v)$ menunjukkan sebuah verteks $u$ di mana terdapat lintasan dari $s$ melalui satu atau beberapa verteks lain sampai ke $v$ dan dilanjutkan ke $u$ yang menghasilkan jarak terpendek. Dalam tahap inisialisasi, $\pi(v)$ untuk setiap verteks $v$ selain $s$ dinyatakan sebagai $\mathtt{NIL}$.

Insisialisasi tersebut dalam bentuk algoritma ditulis sebagai Algoritme~\ref{alg:init-dijkstra}.

\begin{algorithm}
\begin{algorithmic}[1]
	\STATE Init\_Short ( G, s )
	\WHILE{Untuk setiap vertex v anggota graph G}
		\STATE Set jarak s ke v dengan bilangan besar, d[v] = biggest
		\STATE Set v tidak punya predecessor, pred[v] = NIL
	\ENDWHILE
	\STATE Set jarak s dengan NOL
\end{algorithmic}
\caption{Algoritme inisialisasi Dijkstra.} \label{alg:init-dijkstra}
\end{algorithm}

Algoritma Dijkstra merupakan algoritma untuk mencari jarak lintasan terpendek dari suatu vertex ke vertex lainnya pada suatu graph yang semua edgenya mempunyai nilai weight tidak negatif.

Pada algoritma ini dipergunakan himpunan S yang merupakan himpunan vertex telah diproses dan priority queue P yang merupakan himpunan vertex yang akan diproses dengan prioritas. Key dari priority queue tersebut adalah jarak vertex tersebut ke vertex terdekat dalam himpunan S. Karena vertex yang mempunyai prioritas tertinggi adalah vertex dengan jarak terpendek, maka P direpresentasikan sebagai heap yang mempunyai sifat key dari orangtua selalu lebih kecil atau sama dengan key dari anak-anaknya.

Dalam proses, anggota S akan bertambah banyak dan anggota P akan berkurang. Proses akan selesai bila tidak ada lagi vertex yang akan diproses atau P telah merupakan queue yang kosong.

Dengan demikian algoritma Dijkstra dapat ditulis sebagai:

\begin{algorithm}
\begin{algorithmic}[1]
	\STATE SPDijkstra (G, s)
	\STATE Init\_Short ( G, s )
	\STATE Set S sebagai himpunan vertex kosong
	\STATE Buat priority queue P dari semua vertex yang merupakan anggota graph
	\WHILE{Selama P tidak kosong lakukan}
		\STATE Atur kembali P sebagai priority queue
		\STATE u = extract\_min (P)
		\STATE Gabung S dengan { u }
		\FOR{Untuk setiap vertex v yang beradjacent pada u}
			\STATE Relax (u, v, w)
		\ENDFOR
	\ENDWHILE
\end{algorithmic}
\caption{Algoritme Dijkstra.} \label{alg:dijkstra}
\end{algorithm}

Karena pada akhirnya S akan beranggotakan seluruh vertex pada graph G yang terhubung dengan vertex asal s, maka dalam implementasi S dapat dibuat sebagai bagian dari struktur data graph G.


\section{Pengkodean Huffman}

Dalam suatu sistem komputer pada umumnya setiap karakter dikodekan dengan jumlah bit yang sama. ASCII mengkodekan setiap karakter dengan 8 bit, oleh karena itu maka untuk suatu file ASCII yang terdiri atas 100 000 karakter diperlukan 800 000 bit tempat penyimpanan data. Bila saja frekuensi dari setiap karakter tersebut tidak sama, maka kebutuhan jumlah tempat penyimpanan data dapat diperkecil dengan cara memberikan kode dengan jumlah bit lebih pendek untuk karakter yang sangat sering muncul. 

Dengan cara berfikir tersebut Huffman membuat algoritma untuk mengkodekan sejumlah karakter dengan jumlah bit sesedikit mungkin. Adapun cara pengkodean Huffman ini dilakukan dengan cara berikut:
\begin{itemize}
\item Atur karakter urut berdasarkan frekuensi terkecil kemunculannya.
\item Buat forest yang terdiri atas tree yang dari masing-masing terdiri atas sebuah node yang merupakan representasi karakter tersebut.
\item Gabungkan tree dari dua node dengan frekuensi terkecil, sehingga terbentuk binary tree dengan root baru dengan frekuensi yang merupakan penjumlahan frekuensi dari node yang digabungkan, anak kiri adalah node yang mempunyai frekuensi lebih kecil dan anak kanan adalah node yang mempunyai frekuensi lebih besar.
\item Urutkan kembali forest tersebut berdasarkan frekuensi terkecil dari root setiap tree.
\item Lakukan kembali penggabungan dua buah tree dengan frekuensi terkecil.
\item Demikian seterusnya hingga terbentuk sebuah binary tree yang disebut Huffman Tree.
\end{itemize}

Untuk dapat membandingkan jumlah bit yang dipergunakan dalam pengkodean biasa dengan pengkodean Huffman perhatikan contoh dibawah ini:

Misal terdapat 8 karakter A, B, C, D, E, F, G dan blank, masing-masing dengan frekuensi sebagai berikut:
\begin{center}
\begin{tabular}{|c|c||c|c|}
	\hline
		Karakter & Frekuensi (\%) & Karakter & Frekuensi (\%) \\
	\hline
		A & 12 & E & 30 \\
		B & 3 & F & 10 \\
		C & 20 & G & 6 \\
		D & 4 & H & 15 \\
	\hline
\end{tabular}
\end{center}
Setiap huruf dalam data tersebut direpresentasikan sebagai sebuah verteks dengan label nama huruf dan frekuensi kemunculannya.

Algoritme Huffman membangun sebuah \emph{Huffman tree} dengan cara membangun serangkaian \emph{Huffman forest}. \emph{Huffman forest} yang pertama dibuat dengan menyusun verteks-verteks huruf tadi berurut berdasarkan frekuensi kemunculannya secara \emph{ascending}, seperti ditunjukkan dalam Gambar~\ref{subfig:huffman-forest-1}. Secara iteratif algoritme Huffman mengambil pasangan verteks atau pasangan \emph{tree} dari \emph{forest} yang memiliki nilai gabungan terkecil. Seperti ditunjukkan dalam Gambar~\ref{subfig:huffman-forest-2}, kita ambil verteks $B$ dan $D$ untuk digabung menjadi sebuah \emph{tree} baru dengan bobot gabungan dari kedua verteks tersebut, yaitu $7$. \emph{Tree} yang baru terbentuk ini kita letakkan pada urutan yang sesuai pada \emph{forest} yang masih tersisa, dalam contoh ini kita letakkan di antara verteks $G$ dan $F$.

\begin{figure}
	\begin{center}
		\subfigure[Langkah 1]{\includegraphics{huffman-forest-1}} \label{subfig:huffman-forest-1}
		\subfigure[Langkah 2]{\includegraphics{huffman-forest-2}} \label{subfig:huffman-forest-2}
		\subfigure[Langkah 3]{\includegraphics{huffman-forest-3}} \label{subfig:huffman-forest-3}
	\end{center}
	\caption{Cara Pembentukan Huffman Tree berdasarkan data pada tabel.} \label{fig:build-huffman-tree}
\end{figure}

\begin{figure}
	\begin{center}
		\includegraphics{huffman-forest-7}
	\end{center}
	\caption{Huffman Tree yang dihasilkan dari proses pada Gambar~\ref{fig:build-huffman-tree}.} \label{fig:huffman-tree}
\end{figure}

Proses pengambilan pasangan verteks atau \emph{tree} seperti ini kita lakukan secara berulang hingga pada akhirnya kita menggabungkan seluruh verteks dalam satu \emph{single tree}, seperti dalam Gambar~\ref{fig:huffman-tree}. \emph{Tree} ini kita gunakan untuk membangun kode Huffman yang diperlukan. Caranya adalah dengan memberi label untuk setiap edge pada \emph{tree} dengan perjanjian bahwa edge untuk anak kiri diberi label $0$ sedangkan edge untuk anak kanan diberi label $1$. Untuk mengetahui kode Huffman dari setiap huruf, kita dapat mengambil jalur mulai dari \emph{root Huffman tree} hingga sampai ke huruf yang ingin kita cari kode Huffman-nya. Sebagai contoh, untuk huruf $H$, kita pergi berawal dari \emph{root} ke anak kanan, lalu ke kiri, dan terakhir ke kanan sampai di verteks $H$, sehingga kita dapatkan kode Huffman untuk $H$ adalah $101$. Selengkapnya kode Huffman untuk masing-masing karakter pada contoh ini diberikan dengan cara sebagai berikut:
\begin{center}
\begin{tabular}{|c|c|c|c||c|c|c|c|}
	\hline
		Karakter & Frekuensi & Kode & Jumlah & Karakter & Frekuensi & Kode & Jumlah \\
			& & Biner & Bit & & & Biner & Bit \\
	\hline
		A & 12 & 011 & 3 & E & 30 & 11 & 2 \\
		B & 3 & 10010 & 5 & F & 10 & 010 & 3 \\
		C & 20 & 00 & 2 & G & 6 & 1000 & 4 \\
		D & 4 & 10011 & 5 & H & 15 & 101 & 3 \\
	\hline
\end{tabular}
\end{center}

Satu hal yang perlu kita kaji lebih jauh adalah efisiensi yang didapatkan jika kita menyimpan huruf-huruf pada contoh ini dengan kode Huffman dibandingkan dengan jika disimpan dengan kode ASCII.

Jika kita misalkan jumlah total kemunculan seluruh huruf adalah 100, maka masing-masing huruf menyumbang beberapa bit sesuai panjang bit untuk huruf tersebut sesuai kode Huffman-nya. Jika kita hitung, total jumlah bit yang diperlukan adalah:
\[
12 \times 3+3 \times 5+20 \times 2+4 \times 5+30 \times 2+10 \times 3+6 \times 4+15 \times 3 = 270 \mathrm{bit}
\]
Bila saja kumpulan karakter tersebut dikodekan dengan cara biasa, yaitu  menggunakan 3 bit per karakter (3 bit mampu merepresentasikan 8 hal yang berbeda), maka jumlah bit yang diperlukan adalah 300 bit, karena setiap huruf menyumbang 3 bit, sedangkan total huruf yang ada adalah 100 buah. Dengan demikian kita dapat hitung efisiensi yang didapatkan dengan menyimpan distribusi huruf ini dengan kode Huffman adalah: $\frac{300-270}{300} \times 100\%=10\%$.

\begin{algorithm}
\begin{algorithmic}[1]
	\STATE \textsc{Huffman} $(C)$
	\COMMENT Array $C$ berisi sekumpulan karakter beserta dengan frekuensi kemunculannya
	\STATE $n \leftarrow \mathrm{len}(C)$
	\STATE $Q \leftarrow $\textsc{PriorityQ}$(C)$
	\FOR{\(i \leftarrow 1\) to \(n-1\)}
	  \STATE \(z \leftarrow \) \textsc{AllocateNode()}
	  \COMMENT Buat node baru \(z\)
	  \STATE \(x \leftarrow \) \textsc{ExtractMin} \((Q)\)
	  \STATE \(y \leftarrow \) \textsc{ExtractMin} \((Q)\)
	  \STATE \(z \cdot \mathrm{left} \leftarrow x\)
	  \STATE \(z \cdot \mathrm{right} \leftarrow y\)
	  \STATE \(z \cdot \mathrm{freq} \leftarrow x \cdot \mathrm{freq} + y\cdot \mathrm{freq}\)
	  \STATE \textsc{Enqueue} \((Q,z)\)
	  \COMMENT Sisipkan $z$ ke dalam \emph{priority queue} $Q$
	\ENDFOR
	\STATE return \textsc{ExtractMin} \((Q)\)
\end{algorithmic}
\caption{Algoritma Huffman.} \label{alg:huffman}
\end{algorithm}

Algoritma Huffman dalam bentuk pseudocode ditunjukkan dalam Algoritme~\ref{alg:huffman}. Dalam algoritme tersebut, digunakan sebuah struktur data \index{priority queue@\emph{priority queue}} \emph{priority queue}. Struktur data ini memiliki sifat FIFO seperti pada \emph{queue} biasa, di mana elemen-elemen disisipkan pada sisi \emph{rear} atau \emph{tail}, sedangkan proses pengambilan dilakukan dari sisi \emph{head} atau \emph{front}. Pada \emph{priority queue} sebuah elemen dijinkan untuk disisipkan di antara elemen-elemen yang sudah ada, tidak harus melalui sisi \emph{rear}. Artinya, sebuah elemen yang baru disisipkan boleh 'mendahului' elemen yang ada pada ujung paling belakang. Ijin ini diberikan jika elemen baru tersebut memiliki prioritas 'lebih tinggi' daripada elemen-elemen yang dia dahului. Dalam kasus \emph{Huffman code}, prioritas sebuah elemen ditentukan dari nilai frekuensi sebuah elemen atau verteks, atau bisa juga nilai frekuensi dari gabungan beberapa elemen huruf yang sudah membentuk sebuah \emph{tree}.


\subsection{Prefix Code} \label{sect:prefix-code}

Satu hal yang membuat \emph{Huffman Code} bermanfaat adalah bahwa tidak mungkin muncul kesalahan interpretasi ketika kita menerima urutan kode biner dalam kode \emph{Huffman}. Sifat semacam ini disebut sebagai sifat \index{prefix code@\emph{prefix code}} \emph{Prefix Code}.


\section{Latihan}

\begin{ExerciseList}
  \Exercise \label{ex:pekerjaan} Kecepatan pekerja A, B, C dan D dalam melakukan pekerjaan 1, 2, 3 dan 4 masing-masing adalah sebagai berikut:
  
  \begin{center}
		\begin{tabular}{|c|c|c|c|c|}
			\hline
					& Tugas 1 & Tugas 2 & Tugas 3 & Tugas 4 \\
			\hline
			\hline
				A & 9 & 2 & 7 & 8 \\
				B & 6 & 4 & 3 & 7 \\
				C & 5 & 8 & 1 & 8 \\
				D & 7 & 6 & 9 & 4 \\
			\hline
		\end{tabular}
  \end{center}
  
  Buatlah algoritma greedy untuk menetapkan tugas yang harus dikerjakan masing-masing pekerja.
  
  \Exercise Gambarkan graf berbobot yang anda gunakan dalam menjawab latihan Soal~\ref{ex:pekerjaan}.
  
  \Exercise Buktikan bahwa suatu graf berbobot terhubung yang setiap edgenya mempunyai bobot yang berbeda, hanya akan mempunyai satu \emph{minimum spanning tree}
  
  \Exercise \label{ex:find-mst} Dari graf pada Gambar~\ref{fig:ex:prim-kruskal}, carilah \emph{minimum spanning tree} dengan menggunakan algoritme Prim dan Kruskal. Pilih sembarang verteks sebagai \emph{source vertex} untuk algoritme Prim. Bandingkan hasil yang didapatkan oleh masing-masing algoritme.
  \begin{figure}
		\begin{center}
		  \resizebox*{0.7\textwidth}{!}{
				\includegraphics{graph-for-mst-1}
			}
			\caption{Minimum Spanning Tree} untuk Soal~\ref{ex:find-mst}. \label{fig:ex:prim-kruskal}
		\end{center}
	\end{figure}
	
	\Exercise Bila  \(G=(V,E)\) merupakan suatu graph tak terhubung, manakah diantara kedua algoritma tersebut yang dapat menghasilkan \index{minimum spanning tree@\emph{minimum spanning tree}!forest@\emph{forest}} \index{minimum spanning forest@\emph{minimum spanning forest}} \emph{minimum spanning forest} (\emph{forest} di mana setiap \emph{tree}-nya adalah \emph{minimum spanning tree}).
	
	\Exercise Dengan menggunakan pengetahuan dalam pencarian \emph{minimum spanning tree}, buatlah algoritma untuk mencari \emph{maximum spanning tree}.
	
	\Exercise Algoritme mana yang memiliki kompleksitas lebih rendah, Kruskal atau Prim? Dalam kondisi seperti apa algoritme Kruskal memiliki kompleksitas lebih rendah daripada algoritme Prim? Dalam kondisi seperti apa keadaan sebaliknya terjadi?
	
	\Exercise \label{ex:dijkstra} Carilah jarak terdekat verteks \(a\) terhadap setiap verteks lainnya pada graf dalam Gambar~\ref{fig:ex:dijkstra}.
	\begin{figure}
		\begin{center}
%			Place 2 rows of vertices: a and b; c, d, and f. Draw weighted directed edges from a to b (4); a to c (3); b to f (6); c to d (7); d to a (2); d to b (5); f to d (4).
      \includegraphics{graph-for-dijkstra-1}
		\end{center}
		\caption{Graf untuk Soal~\ref{ex:dijkstra}} \label{fig:ex:dijkstra}
	\end{figure}
	
	\Exercise \label{ex:dijkstra-negative-edge} Algoritme Dijkstra yang dibahas dalam buku ini menggunakan bobot tiap edge dengan nilai positif. Apa yang terjadi jika terdapat satu atau beberapa edge dalam sebuah graf yang bernilai negatif? Diskusikan dengan membuat sebuah graf sebagai contoh.
	
	\Exercise Berapakah tinggi maksimum suatu Huffman tree untuk mengkodekan $n$ buah karakter?
	
	\Exercise \label{ex:huffman} Suatu dokumen hanya terdiri dari karakter A, I, U, E dan O, dengan jumlah masing-masing karakter adalah 35\%, 10\%, 20\%, 20\% dan 15\% ingin dikirim melalui jaringan komputer. Berikanlah pengkodean untuk setiap karakter tersebut agar biaya pengiriman minimal.
	
	\Exercise Hitunglah kompleksitas algoritme Huffman jika diberikan masukan $n$ simbol berbeda dengan frekuensi kemunculan setiap simbol $p_{1}, p_{2}, \ldots p_{n}$.
	
	\Exercise Hitung efisiensi yang didapatkan dari pengkodean pada Soal~\ref{ex:huffman} dibandingkan jika huruf-huruf tersebut disimpan dengan kode ASCII-7 bit.
	
	\Exercise Bagaimana jika dalam penyusunan \emph{Huffman tree} didapatkan sebuah pasangan \emph{tree} atau verteks yang memiliki bobot yang sama?
\end{ExerciseList}
